import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1125 {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int[] f=new int[1<<req_skills.length];
        int[] pre=new int[1<<req_skills.length];
        int[] record=new int[1<<req_skills.length];
        Map<String,Integer> map=new HashMap<>();
        for (int i=0;i<req_skills.length;i++){
            map.put(req_skills[i],i);
        }
        Arrays.fill(f,-1);
        f[0]=0;
        for (int i=0;i<f.length;i++){
            if (f[i]!=-1){
                for (int j=0;j<people.size();j++) {
                    List<String> person=people.get(j);
                    int state=i;
                    for (String s : person) {
                        state=state|(1<<map.get(s));
                    }
                    if (f[state]==-1 || f[state]>f[i]+1){
                        f[state]=f[i]+1;
                        pre[state]=i;
                        record[state]=j;
                    }
                }
            }
        }
        int[] ans=new int[f[f.length-1]];
        int count=0,t=f.length-1;
        while (t!=0){
            ans[count++]=record[t];
            t=pre[t];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1125().smallestSufficientTeam(new String[]{"algorithms", "math", "java", "reactjs", "csharp", "aws"}, Arrays.asList(Arrays.asList("algorithms", "math", "java"), Arrays.asList("algorithms", "math", "reactjs"), Arrays.asList("java", "csharp", "aws"), Arrays.asList("reactjs", "csharp"), Arrays.asList("csharp", "math"), Arrays.asList("aws", "java")))));
    }
}
